//算法6.2　采用邻接表表示法创建无向图

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MVNum 100                        	//最大顶点数 
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef char VerTexType;					//顶点信息
typedef int OtherInfo;						//和边相关的信息 

//- - - - -图的邻接表存储表示- - - - - 
typedef struct ArcNode{                		//边结点 
    int adjvex;                          	//该边所指向的顶点的位置 
    struct ArcNode *nextarc;          		//指向下一条边的指针 
    OtherInfo info;                      	//和边相关的信息 
}ArcNode; 

typedef struct { 
    VerTexType data;                    	//顶点信息 
    ArcNode *firstarc; 	            		//指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum];               		//AdjList表示邻接表类型 

typedef struct{ 
    AdjList vertices;                 		//邻接表 
    int vexnum, arcnum;              		//图的当前顶点数和边数 
}ALGraph;

bool visited[MVNum]={false};           				//访问标志数组，其初值为"false" 
bool b_visited[MVNum]={false};           				//访问标志数组，其初值为"false" 
typedef struct {
	VerTexType base[MVNum]; //队列中数据元素类型为VerTexType
	int front; //头指针
	int rear; //尾指针
} SqQueue;

SqQueue BQ; //存放队列

int InitQueue(SqQueue *Q) {//构造一个空队列Q
	Q->front = Q->rear = 0; //头指针和尾指针置为零，队列为空
	return OK;
}

int EnQueue(SqQueue *Q, VerTexType *e) {//插入元素e为Q的新的队尾元素
	if ((Q->rear + 1) % MVNum == Q->front) //尾指针在循环意义上加1后等于头指针，表明队满
		return ERROR;
	Q->base[Q->rear] = *e; //新元素插入队尾
	Q->rear = (Q->rear + 1) % MVNum; //队尾指针加1
	return OK;
}

int QueueEmpty(SqQueue *Q) {
	if (Q->front == Q->rear) //队空
		return OK;
	else
		return ERROR;
}

int DeQueue(SqQueue *Q, VerTexType *e)//删除Q的队头元素，用e返回其值
{
	if (Q->front == Q->rear)
		return ERROR; //队空
	*e = Q->base[Q->front]; //保存队头元素
	int k = Q->front; //保存队头元素的位置
	Q->front = (Q->front + 1) % MVNum; //队头指针加1
	return k;
}
int LocateVex(ALGraph G , VerTexType v){
	//确定点v在G中的位置
	for(int i = 0; i < G.vexnum; ++i)
		if(G.vertices[i].data == v)
			return i;
   return -1;
}//LocateVex

ALGraph CreateUDG(){ 
	//采用邻接表表示法，创建无向图G
	int i , k;
	char c;
	printf("请输入总顶点数:");
	ALGraph G;
	scanf("%d%c",&G.vexnum,&c);
	printf("请输入总边数:");
	scanf("%d%c",&G.arcnum,&c);				//输入总顶点数，总边数 
    printf("\n");
	
	for(i = 0; i < G.vexnum; ++i){          	//输入各点，构造表头结点表
		printf("请输入第%d个点的名称:",(i));
		scanf("%c%c",&G.vertices[i].data,&c);           	//输入顶点值 
		G.vertices[i].firstarc=NULL;			//初始化表头结点的指针域为NULL 
    }//for
	
	printf("请输入一条边依附的顶点,如 a b\n");
	for(k = 0; k < G.arcnum;++k){        		//输入各边，构造邻接表
		VerTexType v1 , v2;
		int i , j;
		printf("请输入第%d条边依附的顶点:",(k + 1),"");
		scanf("%c%c",&v1,&c);
		scanf("%c%c",&v2,&c);//输入一条边依附的两个顶点
		i = LocateVex(G, v1);  
		j = LocateVex(G, v2);
		//确定v1和v2在G中位置，即顶点在G.vertices中的序号 

		ArcNode *p1=(ArcNode *)malloc(sizeof(ArcNode));               	//生成一个新的边结点*p1 
		p1->adjvex=j;                   		//邻接点序号为j 
		p1->nextarc= G.vertices[i].firstarc;  G.vertices[i].firstarc=p1;  
		//将新结点*p1插入顶点vi的边表头部

		ArcNode *p2=(ArcNode *)malloc(sizeof(ArcNode));     //生成另一个对称的新的边结点*p2 
		p2->adjvex=i;                   		//邻接点序号为i 
		p2->nextarc= G.vertices[j].firstarc;  G.vertices[j].firstarc=p2; 
		//将新结点*p2插入顶点vj的边表头部 
    }//for 
    return G; 
}//CreateUDG
void DFS(ALGraph G, int v){        				//图G为邻接表类型 
	printf("%c ",G.vertices[v].data);  
	visited[v] = true;    						//访问第v个顶点，并置访问标志数组相应分量值为true 
	ArcNode *p = G.vertices[v].firstarc;		//p指向v的边链表的第一个边结点 
	while(p != NULL){              				//边结点非空 
		int w = p->adjvex;               		//表示w是v的邻接点 
		if(!visited[w])  DFS(G, w);   			//如果w未访问，则递归调用DFS 
		p = p->nextarc;                			//p指向下一个边结点 
	} 
}
void BFS (ALGraph G, int v){ 
    //按广度优先非递归遍历连通图G 
	SqQueue Q;
	VerTexType u;
	int f;


	VNode temp = G.vertices[v];

    printf("%c ",temp.data);    
	b_visited[v] = true;     						//访问第v个顶点，并置访问标志数组相应分量值为true 
    InitQueue(&Q);              													//辅助队列Q初始化，置空         
    EnQueue(&Q, &temp.data);            													//v进队 
    while(!QueueEmpty(&Q)){//队列非空 
		DeQueue(&Q, &u); 
		f=LocateVex(G,u);
		ArcNode *p = G.vertices[f].firstarc;										//队头元素出队并置为u
		//for(w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)){
		while(p){
			int w = p->adjvex;//表示w是v的邻接点
			//依次检查u的所有邻接点w
			if(!b_visited[w]){//w为u的尚未访问的邻接顶点 
				temp = G.vertices[w];
				printf("%c ",temp.data);
				b_visited[w] = true;//访问w，并置访问标志数组相应分量值为true 
				EnQueue(&Q, &temp.data);//w进队 
			}//if
			p = p->nextarc;                			//p指向下一个边结点 
		}//for
    }//while 
}//BFS
int main(){
	printf("************算法6.2　采用邻接表表示法创建无向图**************");
	ALGraph G=CreateUDG();
	int i;

	printf("*****邻接表表示法创建的无向图*****\n");
	
	for(i = 0 ; i < G.vexnum ; ++i){
		VNode temp = G.vertices[i];
		ArcNode *p = temp.firstarc;
		if(p == NULL){
			printf("%c",G.vertices[i].data);
		}
		else{
			printf("%c",temp.data);
			while(p){
				printf("->");
				printf("%d",p->adjvex);
				p = p->nextarc;
			}
		}
		printf("\n");
	}
	printf("请输入遍历连通图的起始点：");
	char c;
	char n;
	scanf("%c%c",&c,&n);
	
	i=0;
	for(i = 0 ; i < G.vexnum ; ++i){
		if(c == G.vertices[i].data)
			break;
	}
	printf("\n");
	while(i >= G.vexnum){
		printf("该点不存在，请重新输入！\n");
		printf("请输入遍历连通图的起始点：");
		scanf("%c%c",&c,&n);
		for(i = 0 ; i < G.vexnum ; ++i){
			if(c == G.vertices[i].data)
				break;
		}
	}

	printf("深度优先搜索遍历图结果：\n");
	DFS(G , i);

	//广度优先搜索
	printf("\n广度优先搜索遍历图结果：\n");
	BFS(G, i);

	return 0;
}//main
